package com.zklh.leetcode.top100;

import com.zklh.leetcode.tree.model.TreeNode;

/**
 * 二叉树的最大路径和算法实现
 *
 * @version 1.0
 * @Author tongnan
 * @Date 2023/10/26
 */
public class Solution124 {
    private int maxPathSum = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        dfs(root);
        return maxPathSum;
    }

    public int dfs(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftMaxPathSum = dfs(root.left);
        int rightMaxPathSum = dfs(root.right);
        int currentMaxPathSum = Math.max(root.val, Math.max(0, leftMaxPathSum) + Math.max(0, rightMaxPathSum) + root.val);

        maxPathSum = Math.max(maxPathSum, currentMaxPathSum);

        return Math.max(Math.max(root.val + rightMaxPathSum, root.val + leftMaxPathSum), root.val);
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(-10);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);

        Solution124 solution124 = new Solution124();
        System.out.println(solution124.maxPathSum(root));
    }
}